#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
	// 小顶堆
	class mycomparison {
	public:
		bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
			return lhs.second > rhs.second;
		}
	};
	vector<int> topKFrequent(vector<int>& nums, int k) {
		// 要统计元素出现频率
		unordered_map<int, int> map; // map<nums[i],对应出现的次数>
		for (int i = 0; i < nums.size(); i++) {
			map[nums[i]]++;
		}
		
		// 对频率排序
		// 定义一个小顶堆，大小为k
		priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
		
		// 用固定大小为k的小顶堆，扫面所有频率的数值
		for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
			pri_que.push(*it);
			if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
				pri_que.pop();
			}
		}
		
		// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
		vector<int> result(k);
		for (int i = k - 1; i >= 0; i--) {
			result[i] = pri_que.top().first;
			pri_que.pop();
		}
		return result;
		
	}
};


class Test{
public:
	// 编写小顶堆的排序比较函数
	class myCmp{
	public:
		bool operator()(const pair<int,int> lhs,const pair<int,int> rhs){
			return lhs.second > rhs.second;
		}
	};
	vector<int> topKFrequent(vector<int>& nums,int k){
		// 1. 统计频度
		unordered_map<int,int> map;
		for(int i = 0;i <nums.size();i++){
			map[nums[i]]++;
		}
		// 2. 使用小顶堆对频度进行排序
		priority_queue<pair<int,int>,vector<pair<int,int>>,myCmp> que;
		
		for(unordered_map<int,int>::iterator it = map.begin();it != map.end();it++){
			que.push(*it);
			if(que.size() > k){
				que.pop();
			}
		}
		
		// 3. 倒序遍历小顶堆获取结果
		vector<int> result(k);
		for(int i = k - 1;i >= 0;i--){
			result[i] = que.top().first;
			que.pop();
		}
		return result;
	}
};


int main(){
	
	vector<int> nums{1,1,1,2,2,3};
	int k = 2;
	Test test;
	vector<int> result = test.topKFrequent(nums,k);
	for(int i = 0;i < result.size();i++){
		cout << result[i] << " ";
	}
	cout << endl;
	
	return 0;
}
